package unclassified.medium;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ReconstructOriginalDigitsFromEnglish_423 {
    public String originalDigits(String s) {
        String[] word = {"zero","one", "two", "three", "four","five","six","seven","eight", "nine"};
        int[] priority = new int[]{0, 8, 6, 3, 2, 7, 5, 9, 4, 1};
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            for (char c : word[i].toCharArray()) {
                k = Math.min(k, cnt[c - 'a']);
            }
            for (char c : word[i].toCharArray()) {
                cnt[c - 'a'] -= k;
            }
            while(k-- > 0) {
                sb.append(i);
            }
        }
        char[] chars = sb.toString().toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }
}
